package cn.zzf.algs.note.exercise.sort;

import cn.zzf.algs.note.base.collection.v1.Node;
import cn.zzf.algs.note.base.sort.Sort;
import cn.zzf.algs.note.base.util.SortUtil;

/**
 * 链表排序。
 * 实现对链表的自然排序（这是将链表排序的最佳方法，因为它不需要额外的空间，且运行时间是线性对数级别的）
 * @author GaoFeng2017
 * @date 2020/7/27 16:50
 */
public class Ex_2_2_17_LinkedListSort implements Sort {

    /** 首节点 */
    private Node<Comparable> firstNode;

    /** 尾节点 */
    private Node<Comparable> lastNode;


    @Override
    public void sort(Comparable[] elements) {

        this.firstNode = new Node<>(elements[0], null);
        this.lastNode = this.firstNode;

        // 初始化链表节点
        for (int currentElementIndex = 1; currentElementIndex < elements.length; currentElementIndex++) {
            this.updateLastNode(elements[currentElementIndex]);
        }


        // TODO 当前版本并不是原地归并，而是通过删除原有

        Node<Comparable> midNode = null;
        Node<Comparable> endNode = this.firstNode;

        boolean isFindSecondSubElements = false;

        while (endNode.getNext() != null) {
            if (SortUtil.less(endNode.getNext().getValue(), endNode.getValue())) {
                if (isFindSecondSubElements) {
                    this.merge(midNode, endNode);
                    isFindSecondSubElements = false;
                } else {
                    midNode = endNode;
                    isFindSecondSubElements = true;
                }
            }
            endNode = endNode.getNext();
        }

        if (isFindSecondSubElements) {
            this.merge(midNode, endNode);
        }

        for (int elementsIndex = 0; elementsIndex < elements.length; elementsIndex++) {
            elements[elementsIndex] = this.firstNode.getValue();
            this.firstNode = this.firstNode.getNext();
        }

    }


    private void merge(Node<Comparable> midNode, Node<Comparable> endNode) {

        // 7 6 5 4 3 2 1
        // step-1, firstNode: 7, lastNode: 1, beginNode:7, midNode:null -> 7, endNode: 7 -> 6, isFindSecondSubElements: false -> true
        // 7 6 5 4 3 2 1
        // step-2, firstNode: 7, lastNode: 1 -> 6, beginNode:7, midNode:7, endNode -> 6, isFindSecondSubElements: true -> false
        // 7 6 5 4 3 2 1
        // step-3, merge-loop1, trigger case1, firstNode: 7, leftNode: 7, midNode: 7, midNode.next: 5, rightNode: 6 -> 5, lastNode: 1 -> 6, endNode -> 6
        // 7 5 4 3 2 1 6
        // step-4, merge-loop2, trigger case1, firstNode: 7 -> 6, leftNode: 7 -> 5, midNode: 7, midNode.next: 5, rightNode: 5, lastNode: 6 -> 7
        // 5 4 3 2 1 6 7
        // 技巧: 不管左右谁长或者说谁先取完，直接先取左边，如果左边更小，那么
        Node<Comparable> leftNode = this.firstNode;
        Node<Comparable> rightNode = midNode.getNext();

        // System.out.println("before merge, Nodes: " + this.firstNode.toFormatString() + "\n" + leftNode.toFormatString() + "\n" + rightNode.toFormatString());

        while (leftNode != midNode.getNext() || rightNode != endNode.getNext()) {

            if (leftNode == midNode.getNext()) {
                this.updateLastNode(rightNode.getValue());
                midNode.setNext(rightNode.getNext());
                rightNode = rightNode.getNext();
            } else if (rightNode == endNode.getNext()) {
                this.updateLastNode(leftNode.getValue());
                this.firstNode = leftNode.getNext();
                leftNode = leftNode.getNext();
           } else if (SortUtil.less(rightNode.getValue(), leftNode.getValue())) {
                this.updateLastNode(rightNode.getValue());
                midNode.setNext(rightNode.getNext());
                rightNode = rightNode.getNext();
            } else {
                this.updateLastNode(leftNode.getValue());
                this.firstNode = leftNode.getNext();
                leftNode = leftNode.getNext();
            }

            // System.out.println("in merge, FirstNodes: " + this.firstNode.toFormatString() + "\nLeftNodes" + leftNode.toFormatString() + "\nRightNode" + rightNode.toFormatString());

        }

        // System.out.println("after merge, Nodes: " + this.firstNode.toFormatString() + "\n" + leftNode.toFormatString() + "\n" + rightNode.toFormatString());

    }

    private void updateLastNode(Comparable value) {
        this.lastNode.setNext(new Node<>(value, null));
        this.lastNode = this.lastNode.getNext();
    }


}
